HW#2 --- last modified January 28 2019 19:26:51..

Solution set.

Due date: Mar 5

Files to be submitted:
  Hw2.zip

Purpose:To become more familiar with database record structures, indexes, and B-trees and to experiment with these in a modern DMS

Related Course Outcomes:

The main course outcomes covered by this assignment are:

CLO2 -- Analyze or code a parallel algorithm using a thread library

CLO3 -- Analyze or code a parallel algorithm using a library such as OpenCL

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw2.zip file. The written part should be in a file Hw2.pdf. For the written part of the homework you should write solutions for the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.

1. Do problem 27.1-4 out of CLRS (there is a slight typo in this problem the second use of the word "greedy" should be changed to the word "optimal").
2. Do problem 27.1-5 out of CLRS.
3. Do problem 27.2-4 out of CLRS.
4. Let `A = (a_(ij))` be an `n times n` matrix. Design a multithreaded algorithm which computes `A^m` with work `O(m\cdot n^3)` and span `O(log m log^2 n)`.
5. Suppose we have an array A[1] to A[n] each entry of which has a positive integer. Devise a CREW PRAM algorithm that computes the median of these numbers in `O(log n)` steps using at most `n` processors.

For the coding part of this homework I would like you to write two parallel programs in Java: ThreadInner.java and JoclInner.java. The first program makes use of Java Threads and the second makes use of JOCL jar file that provides Java bindings to OpenCL. Both of these programs should compute the inner product of two vectors of integers that come from a file. I would like you to code both of your programs so that their spans are `O(log n)`. ThreadInner.java a will be compiled from the command line via:

javac JoclInner.java

It can use either classic Java Threads or the Fork Join/Parallel Array frameworks in java.util.concurrent. We didn't talk about the latter so you'll be own your own to learn about if you want to use those. To run your program I will then type:

java ThreadInner filename_with_vector_data

On this input, your program should read in the contents filename_with_vector_data, which should consist of lines with two comma separated integers followed by a new line character/line, make two vectors `vec x` and `vec y` from these, and compute their inner product `vec x \cdot vec y = \sum_i x_iy_i`. Finally, it should output this value followed by a new line. For example, I might have the file my_vectors.txt with contents:

1,-1
2,1
3,4
10,5

This corresponds to the vectors `[1,2,3,10]` and `[-1,1,4,5]` whose inner product is `1\cdot-1 + 2\cdot1 + 3\cdot4+ 10\cdot 5 = 63`. So after running your program, it should output:

63

javac JoclInner.java

You can assume I have set up the classpath to find the JoCL jar file. Then I'll run your program with a line like:

java JoclInner filename_with_vector_data

Your JOCL program will probably need to make multiple calls from the CPU to the GPU.

For each program you should add a mechanism of your choice to time just the portion of the code in which parallel processing is done (not reading in the file, you probably want to be using System.nanoTime()). I want you to do experiments with both programs varying the length of the vectors you compute the inner products of. Look up the number of cores the machine you are experimenting on has, and the number of GPU shader processors it has. If you plot time versus the length of vectors you compute the inner products of, does it match what you'd expect in each case if Brent's Theorem were an equality rather than an inequality? Write up your experiments also in Hw2.pdf. This timing should be turned off by default.

If you want to use Python to do this homework, use the threading library for threads and PyOpenCL for OpenCL. Name your programs: ThreadInner.py and PyOpenCLInner.py respectively.

Point Breakdown